// 《围棋》作者版权所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package ssa

import "cmd/internal/src"

// branchelim试图通过生成CondSelect指令来消除分支。
// 
// 搜索看起来像
// 
// bb0 bb0 
// \/\
// bb1或bb1 bb2的基本块<-简单的if/else块
// 124 BB 18
// 
// 空的（没有副作用）；
// 根据需要在postdominator中重写PHI。
func branchelim(f *Func) {
	// FIXME:添加对更多体系结构上降低条件选择的支持
	switch f.Config.arch {
	case "arm64", "ppc64le", "ppc64", "amd64", "wasm":
		// 实现
	default:
		return
	}

	// 查找计算任何负载地址时使用的所有值。
	// 通常，这些值具有AddPtr、Lsh64x64等操作。
	loadAddr := f.newSparseSet(f.NumValues())
	defer f.retSparseSet(loadAddr)
	for _, b := range f.Blocks {
		for _, v := range b.Values {
			switch v.Op {
			case OpLoad, OpAtomicLoad8, OpAtomicLoad32, OpAtomicLoad64, OpAtomicLoadPtr, OpAtomicLoadAcq32, OpAtomicLoadAcq64:
				loadAddr.add(v.Args[0].ID)
			case OpMove:
				loadAddr.add(v.Args[1].ID)
			}
		}
	}
	po := f.postorder()
	for {
		n := loadAddr.size()
		for _, b := range po {
			for i := len(b.Values) - 1; i >= 0; i-- {
				v := b.Values[i]
				if !loadAddr.contains(v.ID) {
					continue
				}
				for _, a := range v.Args {
					if a.Type.IsInteger() || a.Type.IsPtr() || a.Type.IsUnsafePtr() {
						loadAddr.add(a.ID)
					}
				}
			}
		}
		if loadAddr.size() == n {
			break
		}
	}

	change := true
	for change {
		change = false
		for _, b := range f.Blocks {
			change = elimIf(f, loadAddr, b) || elimIfElse(f, loadAddr, b) || change
		}
	}
}

func canCondSelect(v *Value, arch string, loadAddr *sparseSet) bool {
	if loadAddr.contains(v.ID) {
		// 即将进行的条件移动的结果用于计算加载地址。
		// 我们希望避免在这种情况下生成条件移动
		// 因为加载地址现在将取决于条件的数据。
		// 以前，它只依赖于条件进行控制，如果分支预测良好（或者即使预测不好，如果加载将导致昂贵的缓存丢失），条件会更快。
		// 见第26306期。
		return false
	}
	// 现在，坚持使用适合寄存器的简单标量
	switch {
	case v.Type.Size() > v.Block.Func.Config.RegSize:
		return false
	case v.Type.IsPtrShaped():
		return true
	case v.Type.IsInteger():
		if arch == "amd64" && v.Type.Size() < 2 {
			// amd64不支持带字节寄存器的CMOV 
			return false
		}
		return true
	default:
		return false
	}
}

// 如果可能的话，elimIf将从f中dom开始的单向分支转换为条件移动。
// loadAddr是一组用于计算加载地址的值。
// 这些值不受CMOV生成的影响。
func elimIf(f *Func, loadAddr *sparseSet, dom *Block) bool {
	// 看看dom是否是一个有一只手臂的if，
	// 是微不足道的，由另一只手臂继承。
	if dom.Kind != BlockIf || dom.Likely != BranchUnknown {
		return false
	}
	var simple, post *Block
	for i := range dom.Succs {
		bb, other := dom.Succs[i].Block(), dom.Succs[i^1].Block()
		if isLeafPlain(bb) && bb.Succs[0].Block() == other {
			simple = bb
			post = other
			break
		}
	}
	if simple == nil || len(post.Preds) != 2 || post == dom {
		return false
	}

	// 我们找到了我们的钻石块。
	// 现在决定将“simple”融合到dom+post-
	// 看起来是否有利可图。

	// 检查是否存在网络钓鱼，并且所有这些网络钓鱼都可以安全地重写为CondSelect。
	hasphis := false
	for _, v := range post.Values {
		if v.Op == OpPhi {
			hasphis = true
			if !canCondSelect(v, f.Config.arch, loadAddr) {
				return false
			}
		}
	}
	if !hasphis {
		return false
	}

	// 为指令数选择一个上限
	// 我们愿意执行，只是为了生成一个死
	// 参数来进行选择。在最坏的情况下，这是
	// 执行的无用指令数。
	const maxfuseinsts = 2

	if len(simple.Values) > maxfuseinsts || !canSpeculativelyExecute(simple) {
		return false
	}

	// 用CondSelect指令替换b中的Phi指令
	swap := (post.Preds[0].Block() == dom) != (dom.Succs[0].Block() == post)
	for _, v := range post.Values {
		if v.Op != OpPhi {
			continue
		}
		v.Op = OpCondSelect
		if swap {
			v.Args[0], v.Args[1] = v.Args[1], v.Args[0]
		}
		v.AddArg(dom.Controls[0])
	}

	// 将所有指令放入“dom”
	// 并适当更新CFG。
	dom.Kind = post.Kind
	dom.CopyControls(post)
	dom.Aux = post.Aux
	dom.Succs = append(dom.Succs[:0], post.Succs...)
	for i := range dom.Succs {
		e := dom.Succs[i]
		e.b.Preds[e.i].b = dom
	}

	// 尽最大努力保存附在块上的语句标记。
	simplePos := simple.Pos
	postPos := post.Pos
	simpleStmt := simplePos.IsStmt() == src.PosIsStmt
	postStmt := postPos.IsStmt() == src.PosIsStmt

	for _, v := range simple.Values {
		v.Block = dom
	}
	for _, v := range post.Values {
		v.Block = dom
	}

	// findBlockPos确定b是否包含stmt标记的值
	// 该值的行号与b本身的Pos相同。
	// （即b上的位置实际上是多余的吗？）
	findBlockPos := func(b *Block) bool {
		pos := b.Pos
		for _, v := range b.Values {
			// 查看是否已经存在与simple匹配的stmt标记值。Pos（可能还有post.Pos）
			if pos.SameFileAndLine(v.Pos) && v.Pos.IsStmt() == src.PosIsStmt {
				return true
			}
		}
		return false
	}
	if simpleStmt {
		simpleStmt = !findBlockPos(simple)
		if !simpleStmt && simplePos.SameFileAndLine(postPos) {
			postStmt = false
		}

	}
	if postStmt {
		postStmt = !findBlockPos(post)
	}

	// 如果simpleStmt和/或postsmt仍然是真的，那么就更努力地寻找对应的语句标记新家。

	// setBlockPos确定b是否包含与b本身的Pos具有相同行号的can be语句值
	// 并且
	// 在其上放置一个语句标记，并返回在该操作中是否成功
	// 。
	setBlockPos := func(b *Block) bool {
		pos := b.Pos
		for _, v := range b.Values {
			if pos.SameFileAndLine(v.Pos) && !isPoorStatementOp(v.Op) {
				v.Pos = v.Pos.WithIsStmt()
				return true
			}
		}
		return false
	}
	// 如果有必要和可能，在简单的
	if simpleStmt {
		if setBlockPos(simple) && simplePos.SameFileAndLine(postPos) {
			postStmt = false
		}
	}
	// 如果有必要和可能，在post 
	if postStmt {
		postStmt = !setBlockPos(post)
	}

	// 中为值添加一个标记。在放弃之前（添加此标记是因为它有帮助），尝试“dom”的结尾，如果不可用，则尝试后续块中的值（如果不复杂）。
	if postStmt {
		if dom.Pos.IsStmt() != src.PosIsStmt {
			dom.Pos = postPos
		} else {
			// 尝试后继块
			if len(dom.Succs) == 1 && len(dom.Succs[0].Block().Preds) == 1 {
				succ := dom.Succs[0].Block()
				for _, v := range succ.Values {
					if isPoorStatementOp(v.Op) {
						continue
					}
					if postPos.SameFileAndLine(v.Pos) {
						v.Pos = v.Pos.WithIsStmt()
					}
					postStmt = false
					break
				}
				// 如果postsmt仍然为true，则尽可能标记该块本身
				if postStmt && succ.Pos.IsStmt() != src.PosIsStmt {
					succ.Pos = postPos
				}
			}
		}
	}

	dom.Values = append(dom.Values, simple.Values...)
	dom.Values = append(dom.Values, post.Values...)

	// 垃圾“post”和“simple”
	clobberBlock(post)
	clobberBlock(simple)

	f.invalidateCFG()
	return true
}

// 这是一个有一个前驱的区块平原吗？
func isLeafPlain(b *Block) bool {
	return b.Kind == BlockPlain && len(b.Preds) == 1
}

func clobberBlock(b *Block) {
	b.Values = nil
	b.Preds = nil
	b.Succs = nil
	b.Aux = nil
	b.ResetControls()
	b.Likely = BranchUnknown
	b.Kind = BlockInvalid
}

// 如果可能，elimIfElse会将f中从dom开始的双向分支转换为条件移动。
// loadAddr是一组用于计算加载地址的值。
// 这些值不受CMOV生成的影响。
func elimIfElse(f *Func, loadAddr *sparseSet, b *Block) bool {
	// 查看“b”是否以if/else结尾：它应该有两个继任者，都是BlockPlain 
	// 并由同一个块继承。
	if b.Kind != BlockIf || b.Likely != BranchUnknown {
		return false
	}
	yes, no := b.Succs[0].Block(), b.Succs[1].Block()
	if !isLeafPlain(yes) || len(yes.Values) > 1 || !canSpeculativelyExecute(yes) {
		return false
	}
	if !isLeafPlain(no) || len(no.Values) > 1 || !canSpeculativelyExecute(no) {
		return false
	}
	if b.Succs[0].Block().Succs[0].Block() != b.Succs[1].Block().Succs[0].Block() {
		return false
	}
	// post控制if/else的块
	post := b.Succs[0].Block().Succs[0].Block()
	if len(post.Preds) != 2 || post == b {
		return false
	}
	hasphis := false
	for _, v := range post.Values {
		if v.Op == OpPhi {
			hasphis = true
			if !canCondSelect(v, f.Config.arch, loadAddr) {
				return false
			}
		}
	}
	if !hasphis {
		return false
	}

	// 如果分支更便宜，就不要生成。
	if !shouldElimIfElse(no, yes, post, f.Config.arch) {
		return false
	}

	// 现在我们承诺：重写每个Phi作为条件选择
	swap := post.Preds[0].Block() != b.Succs[0].Block()
	for _, v := range post.Values {
		if v.Op != OpPhi {
			continue
		}
		v.Op = OpCondSelect
		if swap {
			v.Args[0], v.Args[1] = v.Args[1], v.Args[0]
		}
		v.AddArg(b.Controls[0])
	}

	// 将所有这些
	// 块的内容移动到“b”中，并相应地更新CFG边
	b.Kind = post.Kind
	b.CopyControls(post)
	b.Aux = post.Aux
	b.Succs = append(b.Succs[:0], post.Succs...)
	for i := range b.Succs {
		e := b.Succs[i]
		e.b.Preds[e.i].b = b
	}
	for i := range post.Values {
		post.Values[i].Block = b
	}
	for i := range yes.Values {
		yes.Values[i].Block = b
	}
	for i := range no.Values {
		no.Values[i].Block = b
	}
	b.Values = append(b.Values, yes.Values...)
	b.Values = append(b.Values, no.Values...)
	b.Values = append(b.Values, post.Values...)

	// 垃圾站，是的，没有
	clobberBlock(yes)
	clobberBlock(no)
	clobberBlock(post)

	f.invalidateCFG()
	return true
}

// 应该限制否则报告消除分支
// 的估计成本是否低于阈值。
func shouldElimIfElse(no, yes, post *Block, arch string) bool {
	switch arch {
	default:
		return true
	case "amd64":
		const maxcost = 2
		phi := 0
		other := 0
		for _, v := range post.Values {
			if v.Op == OpPhi {
				// 每个phi都会导致CondSelect，它会降低到CMOV，
				// 在大多数CPU上，CMOV的延迟大于1。
				phi++
			}
			for _, x := range v.Args {
				if x.Block == no || x.Block == yes {
					other++
				}
			}
		}
		cost := phi * 1
		if phi > 1 {
			// 如果我们有超过1个phi，并且post中的一些值有参数
			// 在yes或no块中，我们可能必须重新计算条件，因为
			// 这些参数可能会阻塞标志。现在假设所有的操作都会关闭标志。
			cost += other * 1
		}
		return cost < maxcost
	}
}

// 可以推测地执行报告块中的每个值是否都可以被评估，而不会造成任何可观察的副作用（内存
// 访问、恐慌等），执行时间变化除外。它还确保该块不包含我们无法推测执行的任何潜在危险装置。
// 警告：此函数当前无法检测代表
// 指令的值，这些指令的执行需要使用CPU 
// 硬件功能检查进行保护。见第34950期。
func canSpeculativelyExecute(b *Block) bool {
	// 不要融合内存操作、Phi操作、分割（可能会导致恐慌）、
	// 或任何其他有副作用的
	for _, v := range b.Values {
		if v.Op == OpPhi || isDivMod(v.Op) || v.Type.IsMemory() ||
			v.MemoryArg() != nil || opcodeTable[v.Op].hasSideEffects {
			return false
		}
	}
	return true
}

func isDivMod(op Op) bool {
	switch op {
	case OpDiv8, OpDiv8u, OpDiv16, OpDiv16u,
		OpDiv32, OpDiv32u, OpDiv64, OpDiv64u, OpDiv128u,
		OpDiv32F, OpDiv64F,
		OpMod8, OpMod8u, OpMod16, OpMod16u,
		OpMod32, OpMod32u, OpMod64, OpMod64u:
		return true
	default:
		return false
	}
}
